package 回溯;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
public class leetcode78子集 {
	/*
	 * 这个题 有 好几种 递归的  方法  好多种
	 *   卧槽 牛逼   ArrayList   速度 是大于 LinkedList的 能用 ArrayList 就用ArrayList
	 *   这里真的 体现 了多态的  优越性  
	 *   List<List<Integer>> ans = new ArrayList<>();
	 *   ans.add(new ArrayList<>(path));
	 *   ans.add(new LinkedList<>(path));
	 *   以上体现的 就 是 多 态的  优越性
	 */
	public static void main(String []args) {
		int nums[] = {1,2,3};
		System.out.println(solution(nums));
		System.out.println(solution1(nums));
	}
	// 这只能暴力 没办法 优化 对吧 这没有优化的 点
	public static List<List<Integer>> solution(int nums[]){
		List<List<Integer>> ans = new ArrayList<>();
		LinkedList<Integer> path =new LinkedList<>();
		if(nums==null || nums.length==0) {
			return ans;
		}
//		ans.add(new LinkedList<>());
		process(nums,0,path,ans);
		return ans;
	}
	// 虽然 ac了  但是 这个 过程 还是要仔细的 弄明白的 说实话 这种 暴力的 手段 还是值得学习  
	// 注意收集的  元素 是 叶子节点 还是所有的 节点
	public static void process(int nums [],int index,LinkedList<Integer> path,
			List<List<Integer>> ans) {
		// 这种全排列  的 问题 basecase 
//		ans.add(new LinkedList<>(path));
		ans.add(new ArrayList<>(path));
		
		//  这句 代码 放在 这个位置 真的 是 巧妙啊  这是通过 画图分析出来的 
		for(int i = index;i < nums.length;i++) {
			path.add(nums[i]);
			process(nums,i+1,path,ans);
			path.removeLast();
		}
	}
	// 暴力递归 的 另一种写法  并不涉及到 回溯 也是 暴力递归(  还是用到了 回溯 的操作) 就是 把 该问题  抽象成一个 二叉树
	// 当前位置 要或者 不要 
	public static List<List<Integer>> solution1(int nums[]){
		List<List<Integer>> ans = new ArrayList<>();
		LinkedList<Integer> path =new LinkedList<>();
		if(nums.length == 0) {
			return ans;
		}
		process1(nums,0,path,ans);
		return ans;
	}
	public static void process1(int nums[],int index,LinkedList<Integer> path,List<List<Integer>>
	ans) { 
		if(index == nums.length) {
			ans.add(new ArrayList<>(path));
			return ;//  这个return 是必须的
		}
		path.add(nums[index]);
		process1(nums,index+1,path,ans);
		path.removeLast();
		process1(nums,index+1,path,ans);
		
		
	}
	
	
}
